package cn.lishiyuan.leetcode;

import cn.lishiyuan.algorithm.heap.Heap;

import java.util.HashMap;

/**
 * 347. 前 K 个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * k 的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 */
public class LeetCode347 {

    static class Item<T> implements Comparable<Item<T>>{
        T data;
        int count;

        @Override
        public int compareTo(Item<T> o) {
            return count - o.count;
        }
    }

    public static Integer[] resolve (Integer[] nums,int k) {
        Integer[] res = new Integer[k];
        // 先统计
        HashMap<Integer,Item<Integer>> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            Integer num = nums[i];
            Item<Integer> defaultV = new Item<>();
            defaultV.data = num;
            defaultV.count = 0;
            Item<Integer> v = map.getOrDefault(num, defaultV);
            v.count++;
            map.put(num,v);
        }

        Heap<Item<Integer>> heap = new Heap<>(k);
        int i = 0;
        for (Item<Integer> value : map.values()) {
            if(i < k){
                heap.add(value);
            }else {
                // 最小元素小于当前元素则替换掉该元素
                if (heap.top().compareTo(value) < 0){
                    heap.removeTop();
                    heap.add(value);
                }
            }
            i++;
        }

        for (int j = 0; j < k; j++) {
            res[j] = heap.removeTop().data;
        }

        return res;
    }


}
